一、Graph Network [2018]

《Relational inductive biases, deep learning, and graph networks》

1. 摘要：人工智能（Artificial intelligence: AI）最近经历了一场复兴，并在视觉、语言、控制、决策等关键领域取得了重大进展。取得这些进展的部分原因是由于廉价的数据、廉价的计算资源，这符合深度学习的天然优势。然而，在不同压力下发展起来的人类智力，其许多决定性特点对于目前的人工智能方法而言仍然是触不可及的。具体而言，超越经验的泛化能力--人类智力从幼年开始发展的标志--仍然是现代人工智能面临的巨大挑战。

   论文 《Relational inductive biases, deep learning, and graph networks》 认为：组合泛化（combinatorial generalization）是AI 实现人类相似能力的首要任务，而结构化表示和计算（structured representations and computations）是实现该目标的关键。正如生物学把先天（nature）和后天（nurture）相结合，论文摒弃手动设计特征（hand-engineering）、端到端学习（end-to-end learning）之间进行二选一选择的错误做法，而是提倡一种利用它们进行优势互补的做法。

   论文探索深度学习框架中使用关系归纳偏置（relational inductive biases）如何促进对实体（entity）、关系（relation）、以及构成它们的规则（rule）的了解。论文为 AI toolkit 提供了一个新的、具有强大关系归纳偏置的构建块（building block）：Graph Network 。Graph Network 概括和扩展了图上运行的各种神经网络方法，并为操作结构化知识 （manipulating structured knowledge）和产生结构化行为（producing structured behaviors ）提供了直接接口。

   论文讨论Graph Network 如何支持关系推理（relational reasoning）、组合泛化（combinatorial generalization）。这为更复杂、更可解释、更可扩展的推理模式（reasoning pattern）奠定了基础。

   作为论文的补充，作者还发布了一个用于构建 Graph Network 的开源软件库，并演示了如何在实际工作中应用它们。

2. 引言：人类智能的一个重要标志是 “无限使用有限方法” （infinite use of finite means） 的能力，其中一小部分的、有限的原始（如单词 word）可以无限地组合（如构成无限多的句子 sentence）。这反映了组合泛化（combinatorial generalization）的原理，即从已知的构建块（building block）来创建新的推论（inference）、预测（prediction）、行为（behavior）。这里我们探索如何通过将偏置学习（biasing learning）用于结构化的表示和计算（structured representations and computations）从而提高现代 AI 的组合泛化能力，尤其是对图（graph）进行操作的系统。

   人类的组合泛化能力很大程度上取决于我们表达结构（representing structure）和推理关系（reasoning about relations）的认知机制。

   • 我们将复杂系统表示为实体（entity）及其相互作用（interaction）的组合。

   • 我们使用层次结构来抽象细粒度（fine-grained）的差异，并捕获 representations 和 behaviors之间的更一般的共性，比如：同一个物体的一部分、同一个场景的物体、同一个城镇的社区。

   • 我们通过组合熟悉的技能（skills）和惯例（routines）来解决新的问题。

   • 我们通过将两个领域之间的关系结构对齐，并根据其中一个领域的相应知识得出另一个领域的推论来进行类比。

   Kenneth Craik 的 The Nature of Explanation 将世界的组成结构 （compositional structure of the world）和我们内在的心理模型（internal mental model）的组织方式联系起来，即：世界是组合的（compositional），或者至少我们是从组合的角度来理解它的。当我们学习的时候，我们要么将新知识放入现有的结构化表示（structured representations ）中、要么调整结构本身从而更好地适应（和使用）新旧知识。

   自 AI 诞生以来，如何构建具有组合泛化的人工智能系统一直就是 AI 的核心问题，它是很多结构化方法（structured approach）的核心，包括：逻辑（logic）、语法（grammar）、经典规划（classic planning）、图模型（graphical model）、因果推理（causal reasoning）、贝叶斯非参数化（Bayesian nonparametric）以及概率规划（probabilistic programming）。

   所有子领域都集中于显式的以实体（entity）和关系（relation）为中心的学习上，例如关系强化学习（relational reinforcement learning）、统计关系学习（statistical relational learning）。结构化方法对于之前的机器学习如此重要的一个关键原因，部分是因为数据和计算资源的昂贵，而结构化方法强大的归纳偏置（inductive biases）所带来的样本复杂度（sample complexity）的改善是非常有价值的。

   与过去的人工智能方法相比，现代深度学习经常遵循 “端到端”（end-to-end） 的设计理念，强调最小限度的先验表征的、计算的假设（minimal a priori representational and computational assumptions），并力求避免使用显式的结构（explicit structure）和特征工程（hand-engineering）。这种强调（emphasis）和当前的大量廉价数据和廉价计算资源非常契合，也得到了充分的验证。这使得牺牲样本效率（sample efficiency）从而更灵活地学习成为一种理性的选择。从图像分类到自然语言处理，深度学习在很多具有挑战性的领域中取得了令人瞩目的快速发展，这证明了这种极简主义原则（minimalist principle）的成功。一个突出的例子是语言翻译，事实证明 sequence-to-sequence方法非常有效，无需使用显式的解析树（ parse tree）或者语言实体（linguistic entity）之间的复杂关系。

   尽管深度学习取得了巨大成功，但是也有一些严厉的批评：深度学习在复杂的语言和场景理解（complex language and scene understanding）、结构化数据的推理（reasoning about structured data）、训练条件之外的迁移学习（transferring learning beyond the training condition）以及少量经验中学习（learning from small amounts of experience）时面临重大挑战。这些挑战需要组合泛化，因此摒弃组合性（compositionality） 以及显式结构（explicit structure）的方法难以满足这些挑战，这并不奇怪。

   当深度学习的前辈连接主义（connectionist）面临诸如结构性的（structured）、符号性的（ symbolic）立场（position）等类似批评时，有些工作直接地、细致地做出了建设性的努力来解决这些挑战。在诸如模拟制造（analogy-making）、语言分析（linguistic analysis）、符号操作（symbol manipulation）以及其它形式的关系推理之类的领域中，符号主义开发了用于表示和推理结构化对象的各种创新的亚符号（sub-symbolic）方法，以及有关大脑如何工作的更多综合理论（integrative theory）。这些工作还有助于培养更多的深度学习进展（advances），这些进展使用分布式向量表示来捕获文本（text）、图（graph）、代数表达式（algebraic expression）、逻辑表达式（logical expression）、以及程序（programs）中的丰富语义内容。

   我们认为，现代 AI 的关键途径是致力于将组合泛化作为首要任务，并且我们主张采用综合方法（integrative approache）来实现这一目标。正如生物学没有在先天（nature）和后天（nurture）之间进行选择一样（生物学同时利用先天和后天，这种整体效果强于每个部分之和），我们也拒绝这样的观念（即， struture 和 flexibility 在某种程度上是矛盾的或不相容的），并且我们同时拥抱结构和灵活性从而获得它们的互补优势。根据大量最新的一些混合了 structure-based方法、deep learning 方法的案例，我们发现：将当今最好的方法（即 deep learning 方法）和早期算力昂贵时必不可少的方法（即结构化方法）相结合的综合技术具有广阔的前景。

   近年来，在深度学习和结构化方法的交集中出现了一类模型，这些模型聚焦于推理有关显式结构化数据（特别是 graph）的方法。这些方法的共同点是可以对离散实体（entity）以及实体之间的关系（relation）进行计算。这些方法和经典方法不同之处在于：如何学习实体和关系的representation 以及structure ，以及相应的计算，从而缓解了事先需要指定它们的负担。即，这些知识是通过学习而来，而不是预先指定的。至关重要的是，这些方法以特定的体系架构假设的形式引入强烈的关系归纳偏置（relational inductive biases），这些偏置指导这些方法学习实体和关系。我们和很多其他人一起认为，这是类似人类智力的基本组成部分。

   在文章的剩余部分，我们通过关系归纳偏置的角度考察了各种深度学习方法，表明现有方法通常带有关系假设（relational assumptions），这些假设并不总是很明显或者显而易见。然后我们提出了一个基于实体和关系推理的通用框架，我们称之为 Graph Network:GN。GN 统一和扩展了图上运行的现有方法，并描述了使用 Graph Network 作为构建块（building block）来构建强大架构的关键设计原理。我们还发布了一个用于构建 Graph Network 的开源库。

1.1 关系归纳偏置

1.1.1 Relational Reasoning

1. 定义结构（structure）为通过一组已知构建块（building block）组成的产品（product）。结构化表示（Structured representations）捕获了这种组成（composition），如元素（element）的排列（arrangement）。结构化计算（structured computations）以一个整体的方式对所有这些元素及其组合进行操作。关系推理（Relational Reasoning）涉及利用实体（entity）和关系（relation）的组成规则（composed rule），从而操作实体和关系的结构化表示。我们用以下数据来描述认知科学、理论计算机科学、人工智能的相关概念：

   • 实体（entity）：具有属性的元素，如具有大小、质量的物理对象。

   • 关系（relation）：实体之间的属性。如两个对象之间的关系可能包括：相同大小（ same size as）、比.. 更重（heavier than）、距离（distance from）。

     • 关系也可以具有属性。比如 more than X times heavier than 带有一个属性 X，它决定了这个关系取值为 true/false 的阈值。

     • 关系也可能对全局上下文敏感。比如对于石头和羽毛，关系 falls with greater accelaration than 取决于环境是在空气中还是真空中。

     这里我们关注实体之间的成对关系（ pairwise relations ）。

   • 规则（rule）：将实体和关系映射到其它实体和关系的函数，就像一个非二元的逻辑谓词（non-binary logical predicate）。例如 is entity X large?、 is entity X heavier than entity y? 这样的尺度比较（scale comparison）。

     这里我们仅考虑带有一个参数或两个参数、并返回一个属性的规则。

2. 我们以图模型（ graphical model ）来作为机器学习中关系推理的示例性说明。

   图模型可以通过在随机变量之间指定显式的条件独立性来建模复杂的联合分布。这样的模型非常成功，因为它捕获了稀疏结构（sparse structure），而稀疏结构是很多现实世界生成过程（generative processes）的基础，并且它们支持有效的学习和推理算法。

   例如，隐马尔可夫模型可以显式指定条件独立性：

   • 当前状态仅依赖于前一个状态，与其它历史状态无关。

   • 当前观测值仅依赖于当前状态，和其它历史状态、其它观测值无关。

   这和很多现实世界因果过程（causal process）的关系结构非常契合。

3. 明确表达变量之间的稀疏依赖关系提供了各种高效的推断（inference）和推理（reasoning）算法。例如，消息传递算法在图模型内的各个位置之间采用通用的消息传播过程，从而导致一个可组合的（composable）、部分并行化的（partially parallelizable） 推理过程（reasoning procedure），这适用于不同大小和形状的图模型。

1.1.2 Inductive Biases

1. 学习是通过观察世界并与世界互动来理解有用知识的过程，它涉及搜索解空间（space of solutions）以期找到可以更好地解释数据、或获得更高回报的解决方案（solution）。但是在很多情况下，有多种解决方案同样出色。归纳偏置（inductive bias）允许学习算法独立于观测到的数据，从而将一种解决方案（或者解释）优先于另一种解决方案（或解释）。

   在贝叶斯模型中，归纳偏置通常以先验分布的选择（choice）、参数化（parameterization）来表示。而在其它模型中，归纳偏置可能是为避免过拟合而添加的正则化项，也可能被编码到算法本身的体系结构中。

2. 归纳偏置通常以灵活性（flexibility）为代价从而换取改善的样本复杂性（sample complexity），并且可以从偏差-方差平衡（bias-variance tradeoff）的角度来理解。理想情况下，归纳偏置既可以在不显著降低性能的情况下改善对于解空间的搜索，又可以帮助找到理想泛化的解决方案。但是，不匹配（mismatched）的归纳偏置也会引入过强的约束从而导致欠拟合。

3. 归纳偏置可以表达关于数据生成过程（data-generating process）或解空间的假设。例如，当使用一维函数拟合数据时，线性最小二乘法遵循近似函数为线性模型的约束，并且在 $L_2$$L_2$ 惩罚下误差最小。这反映了一个假设：数据生成过程可以简单地解释为被加性高斯噪音（additive Gaussian noise）破坏的线性过程（line process）。

   类似地，$L_2$$L_2$ 正则化倾向于获得参数较小的解，并可以对于病态问题（ill-posed problem）可以得到唯一的解决方案和全局结果。这可以解释为关于学习过程的一种假设：当解决方案之间的分歧较少时，寻找好的解决方案更加容易。

   注意，这些假设不需要明确地解释模型或算法如何与世界交互。

1.1.3 Relational Inductive Biases

1. 机器学习和 AI 中很多具有关系推理能力的方法使用关系归纳偏置（relational inductive bias）。虽然不是精确的正式定义，但是我们通常使用该术语来指归纳偏置（inductive bias），它对于学习过程中实体之间的关系和交互施加了约束。

2. 近年来新型的机器学习体系架构迅速增加，从业人员经常遵循通过组合基本构建块（elementary building block）来形成更复杂、更深计算的层次（hierarchies）和计算图。

   例如：

   • 全连接层（full connected layer）被堆叠到多层感知机（multilayer perceptrons: MLPs）中。

   • 卷积层（convolutional layers）被堆叠到卷积神经网络（convolutional neural networks: CNNs）中。

   • 图像处理网络的标准配置是由各种 CNN 变体 + MLP 的组合。

   这种 layer 的组合提供了一种特殊类型的关系归纳偏置：层次处理（hierarchical processing） 的关系归纳偏置。其中计算分阶段（in stages）进行，这会导致输入信号中的信息之间产生越来越长距离的交互（long range interaction）。

   正如我们在下面探讨的那样，构建块本身也带有各种关系归纳偏置（如下表所述）。尽管超出了本文的范围，但是在深度学习中也使用各种非关系归纳偏置（ non-relational inductive biases），例如：激活值的非线性（non-linearity）、权重衰减、dropout、batch normalization/layer normalization、data augmentation、训练方式、优化算法都对学习的轨迹和结果施加了约束。

   

3. 要探索各种深度学习方法中表达的关系归纳偏置，我们必须确定几个关键因素：实体是什么、关系是什么、组成实体和关系的规则是什么、计算实体和关系的规则是什么。在深度学习中，实体和关系通常表示为分布式表示（distributed representation），规则通常表示为神经网络函数逼近器（approximator）。然后，实体、关系、规则的精确形式在不同体系架构之间有所不同。为了理解架构之间的这些差异，我们通过以下探索进一步理解每种架构如何支持关系推理：

   • 规则函数（rule function）的自变量（argument），例如：哪些实体和关系作为输入。

   • 规则函数如何在计算图上重用或共享，例如：跨不同实体和关系、跨不同时间或 step 。

   • 架构如何定义 representation 之间的交互（interaction）与隔离（isolation）。例如：通过在相关的实体上应用规则来得出结论，而不是对每个实体独立处理。

1.1.4 标准 deep learning 构建块

1. Fully Connected Layers 全连接层：也许最常见的构建块是全连接层。

   通常全连接层被实现为输入向量的非线性函数：

   $$\overrightarrow{\mathbf{h}}=\sigma (\mathbf{W}{\overrightarrow{\mathbf{x}}}_i+\overrightarrow{\mathbf{b}})$$

   其中 $\mathbf{W}$$\mathbf W$ 为权重矩阵，$\overrightarrow{\mathbf{b}}\in {\mathbb{R}}^n$$\mathbf{\vec b}\in \mathbb R^{n}$ 为偏置向量， ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^n$$\mathbf{\vec x}_i\in \mathbb R^n$ 为输入向量， $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数。

   因此实体是网络中的单元，关系是 all-to-all：

   • 所有输入单元都连接到所有输出单元，规则由权重矩阵和偏置向量指定。

   • 规则的自变量是完整的输入信号，没有参数共享，也没有信息隔离。

   因此，在全连接层中的隐式关系归纳偏置非常弱（week）：所有输入单元之间可以交互从而决定任何输出单元的值，并且所有输出单元之间相互独立。

2. Convolutional Layers 卷积层：另一个常见的构建块是卷积层。

   卷积层通常被实现为输入向量或张量的卷积：

   $$\mathbf{H}=\sigma (\mathbf{X}\ast \mathbf{K}+\mathbf{B})$$

   其中 $\mathbf{K}$$\mathbf K$ 为卷积核， $\mathbf{X}$$\mathbf X$ 为输入张量， $\ast$$*$ 为卷积算子， $\mathbf{B}$$\mathbf B$ 为偏置张量， $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数。

   这里的实体仍然是单个单元（或者网格元素，如像素），但是实体之间的关系更为稀疏。全连接层和卷积层之间的差异在于卷积层增加了一些重要的关系归纳偏置：局部性（locality）和平移不变性（translation invariance）。

   • 局部性反映了关系规则（relational rule）的自变量是那些在输入信号的坐标空间中紧密相邻的实体、并且和远处实体隔离。

   • 平移不变性反映了在输入中跨区域重复使用相同的规则。

   这些偏置对于处理天然的图像数据非常有效，因为图像数据局部邻域内存在较高的协方差，且随着距离增加，协方差会减小。并且统计量在整个图上大多是平稳的（stationary）。

3. Recurrent Layers 递归层：第三种常用的构建块是递归层，它是通过一系列 step 来实现的。这里我们将每个 step 的输入和 hidden state 视为实体，将马尔可夫过程视为关系：当前 hidden state 依赖于前一个 hidden state 和当前 input。实体组合的规则将当前 step 的输入、前一个 hidden state 作为规则的自变量，然后更新当前 hidden state 。

   这个规则在每个 step 被复用，这反映了时间不变性（类似于 CNN 在空间上的平移不变性）的关系归纳偏置。例如，某些物理事件序列的结果不应该取决于一天中的某个时刻。

   RNN 也通过其马尔可夫结构对序列带来局部性（locality）的 bias 。

4. 下图给出了常见的深度学习构建块中的复用和共享，共享的权重由具有相同颜色的箭头表示。

   • (a)：全连接层，其中所有权重都是独立的，并且没有共享。

   • (b) ：卷积层，其中局部核函数在输入中多次重复使用。

   • (c)：循环层，其中相同的函数可以在不同的 step 中复用（水平方向代表了时间线）。

   

1.1.5 sets 和 graphs 上的计算

1. 虽然标准的深度学习工具包所包含的方法具有各种形式的关系归纳偏置，但是没有默认的深度学习组件可以在任意关系结构上运行。我们需要模型具有显式的实体表示和关系表示，并需要学习算法，该算法用于找到计算实体和关系交互的规则、以及将规则置于数据中的方式。

   重要的是，世界上的实体（如对象、agent）没有自然顺序。相反，可以通过关系的性质来定义顺序。如：可以根据对象之间的大小、质量、年龄、毒性、价格之间的关系来对它们进行排序。顺序不变性（invariance to ordering）（除了处理关系时）是一种理想的属性，这种不变性应该由用于关系推理的深度学习组件来反映。

2. 集合（sets）是描述包含一组无序实体的系统的自然表达形式。具体而言，集合的关系归纳偏置并不是来自于 something 的存在，而是来自于 something 的缺失。

   为了说明，考虑由 $n$$n$ 个行星组成的太阳系，我们的任务是预测系统的质心。行星的属性包括质量、位置、速度等。第 $i$$i$ 个行星的属性记作向量 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 。对于该任务，行星之间的顺序并不重要，因为系统状态（即质心）只能用聚合的、平均的统计量来描述。

   但是，如果要使用 MLP 来预测该任务，即使已经知道了特定顺序输入 $({\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_n)$$(\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots, \mathbf{\vec x}_n)$ 的预测，也不一定能够迁移到不同顺序、相同输入的预测 $({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{\mathbf{x}}}_1,\cdots ,{\overrightarrow{\mathbf{x}}}_2)$$(\mathbf{\vec x}_n,\mathbf{\vec x}_1,\cdots, \mathbf{\vec x}_2)$ 。这是因为这里有 $n!$$n!$ 种可能的排列组合，因此最坏的情况下 MLP 可能会认为每种顺序从根本上看是不同的，因此需要指数级的输入/输出训练样本来学习近似函数。

   处理类似组合爆炸的自然方法是允许预测依赖于输入的对称函数。这可能意味着首先计算 per-object 参数共享的特征 $\{f({\overrightarrow{\mathbf{x}}}_1),\cdots ,f({\overrightarrow{\mathbf{x}}}_n)\}$$\{f(\mathbf{\vec x}_1),\cdots,f(\mathbf{\vec x}_n)\}$ ，然后将它们以对称的方式聚合，如均值聚合。这种方式是 Deep Sets 以及相关模型的本质。我们在后文进一步讨论。

3. 当然，在很多问题中排列不变性（permutation invariance）并不是底层结构的唯一重要形式。例如，一个集合中的每个对象都可能受到集合中其它对象的 pairwise interaction 的影响。在我们的行星case 中，考虑在时间间隔 $\mathrm{\Delta }t$$\Delta t$ 之后预测每个行星位置的任务。这种情况下，使用聚合的平均信息是不够的，因为每个行星的运动取决于其它行星所施加的力。

   取而代之的是，我们可以将每个对象的状态计算为 ${\overrightarrow{\mathbf{x}}}_i^{\prime }=f({\overrightarrow{\mathbf{x}}}_i,\sum _{j}g({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j))$$\mathbf{\vec x}_i^\prime = f\left(\mathbf{\vec x}_i, \sum_j g\left(\mathbf{\vec x}_i,\mathbf{\vec x}_j\right)\right)$ ，其中：

   • $g({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)$$g\left(\mathbf{\vec x}_i,\mathbf{\vec x}_j\right)$ 可以计算第 $j$$j$ 颗行星作用在第 $i$$i$ 颗行星上的力。

   • $f({\overrightarrow{\mathbf{x}}}_i,\cdot )$$f(\mathbf{\vec x}_i,\cdot )$ 可以计算出第 $i$$i$ 颗行星的未来状态，该状态是由力和动力学方程产生的。

   我们在各处都使用相同的 $g(\cdot ,\cdot )$$g(\cdot,\cdot)$ 表明系统的全局排列不变性（global permutation invariance）。但是，它也支持不同的关系结构，因为 $g(\cdot ,\cdot )$$g(\cdot,\cdot)$ 现在采用两个自变量，而不是一个。

4. 上述太阳系的例子说明了两种关系结构 （relation structure）：一种完全没有关系，一种包含所有的 pairwise 关系。很多现实世界的系统（如下图所示）的关系结构在这两种极端 case 之间：某些实体 pair 对之间存在关系、另一些实体 pair 对之间缺乏关系。

   在我们的太阳系例子中，如果该系统改为由行星及其卫星组成，则可能会试图通过忽略不同行星的卫星之间的相互作用来近似。实际上，这意味着仅计算某些对象之间的交互，即：

   $${\overrightarrow{\mathbf{x}}}_i^{\prime }=f({\overrightarrow{\mathbf{x}}}_i,\sum _{j\in \delta (i)}g({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j))$$

   其中 $\delta (i)\subseteq \{1,2,\cdots ,n\}$$\delta(i)\sube \{1,2,\cdots,n\}$ 为节点 $i$$i$ 的邻居集合 。这对应于一个图（graph），因为第 $i$$i$ 个对象仅与剩余对象的一个子集交互，这个子集由对象 $i$$i$ 的邻域描述。

   注意：节点 $i$$i$ 更新后的状态仍然不依赖于我们描述邻居的顺序。

   下图为现实世界的不同系统，以及对应的graph 的表达：

   • (a) ：一个分子图，其中每个原子表示为一个节点，边对应于化学键。

   • (b)：一个质点弹簧系统，其中绳索由一个质点序列定义，这些质点在图中表示为节点。

   • (c)：一个 n body 系统，其中每个 body 为节点，节点之间全连接。

   • (d)：一个刚体系统，其中球和墙壁都为节点，底层的 graph 定义了球之间、球和墙壁之间的相互作用。

   • (e)：一个句子，其中单词对应于解析树上的叶结点，其它节点和边可以由解析器提供。或者也可以使用一个全连接的图。

   • (f)：一张图片，可以将其分解为图像块（patch），每个块代表一个节点，并且节点之间全连接。

   

5. 通常，图（graph）是支持任意 pairwise 关系结构的表示形式，并且图上的计算提供了超越卷积层、递归层的强大的关系归纳偏置。

1.2 Graph Network

1. 图神经网络已经在监督学习、半监督学习、无监督学习、强化学习领域被应用。

   • 图神经网络被认为在具有丰富的关系结构的任务上很有效，例如视觉场景理解（visual scene understanding）任务、few-shot learning 任务等。

   • 图神经网络也被用于物理系统（physical system）和多智体系统（multi-agent system），从而推理知识图谱、预测分子化学性质、预测道路交通流量、分类和分割图像/视频/3D 网格/点云、分类图像中的区域、执行半监督文本分类及机器翻译。

   • 图神经网络已经在 model-free 和 model-based 连续控制中都被使用，用于 model-free 的强化学习，以及更经典的规划问题。

   • 图神经网络还探索了很多涉及离散实体和结构推理的传统计算机科学问题，例如组合优化、布尔满足性（satisfiability）、程序表示和验证、元胞自动机及图灵机建模，以及图模型上的 inference。最近的工作还关注于图的生成模型、graph embedding 的无监督学习。

2. 这里介绍我们的图网络框架 Graph Networks: GN，该框架定义了一族函数用于图结构表示（graph-structured representations）的关系推理（relational reasoning）。我们的 GN 框架概括并扩展了各种图神经网络、MPNN、以及 NLNN 方法，并支持从简单的构建块构建复杂的体系架构。

   注意，我们避免在 Graph Network 中使用术语 neural 来反映GN 可以使用除神经网络以外的函数来实现，尽管这里我们的重点是神经网络的实现。

3. GN 框架中的主要计算单元是 GN 块（GN block）。GN 块是一个 graph-to-graph 的模块，它将图作为输入，对结构进行计算，然后将图作为输出返回。图的节点表示实体，图的边表示关系，图的全局属性表示 system-level 属性。

   • GN 框架的 block 组织强调可定制性（customizability），以及综合了新的架构，这个新架构能够表达预期的关系归纳偏置。

   • GN 框架的主要设计原则是：灵活的表示形式（flexible representations）、可配置的块内结构（configurable within-block structure）、可组合的多块体系架构（composable multi-block architectures）。

4. 我们引入一个例子来更具体的说明 GN。可以在任意重力场中预测一组橡胶球的运动，这些橡胶球不会彼此弹跳，而是每个橡胶球都有一个或多个弹簧，这些弹簧将它们和其它橡胶球相连。我们将在下文中参考这个例子，从而启发 （motivate）图的表示以及图上进行的计算。

1.2.1 图的定义

1. 这里我们使用图来表示带全局属性的、有向的、带属性的多图（multi-graph）。

   • 带全局属性：每个图具有一个 graph-level 属性 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 。

   • 有向的：每条边 $k$$k$ 具有两个节点：sender 节点 $s_k$$s_k$ （即起点）、receiver 节点 $r_k$$r_k$ （即终点）。

   • 带属性的：每个节点 $i$$i$ 都带有与之关联的节点属性，每条边 $k$$k$ 都带有与之关联的边属性。

   • 属性：节点、边、图的属性可以编码为向量、集合、甚至另一个图。

   • 多图（multi-graph）：节点之间可能存在多条边，包括自连接（ self-edge ）。

   

2. 在我们的 GN 框架内，图被定义为三元组 $\mathcal{G}=(\overrightarrow{\mathbf{u}},\mathcal{V},\mathcal{E})$$\mathcal G = \left(\mathbf{\vec u},\mathcal V, \mathcal E\right)$ ，其中：

   • $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 为全局属性，比如它代表全局的万有引力场。

   • $\mathcal{V}=\{{\overrightarrow{\mathbf{v}}}_i{\}}_{i=1}^{N_v}$$\mathcal V = \{\mathbf{\vec v}_i\}_{i=1}^{N_v}$ 代表节点属性的集合， $N_v$$N_v$ 为节点数量， ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 为节点 $i$$i$ 的属性。例如： $\mathcal{V}$$\mathcal V$ 可能代表橡胶球集合，每个橡胶球都包含位置、速度、质量等属性。

   • $\mathcal{E}=\{({\overrightarrow{\mathbf{e}}}_k,r_k,s_k){\}}_{k=1}^{N_e}$$\mathcal E = \{(\mathbf{\vec e}_k, r_k,s_k)\}_{k=1}^{N_e}$ 为边的集合， $N_e$$N_e$ 为边数量， ${\overrightarrow{\mathbf{e}}}_k$$\mathbf{\vec e}_k$ 为边的属性， $r_k$$r_k$ 为 receiver 节点， $s_k$$s_k$ 为 sender 节点。例如：$\mathcal{E}$$\mathcal E$ 可能代表不同橡胶球之间的弹簧，边的属性为弹簧系数。

1.2.2 GN block

1. 一个 GN 块包含三个更新函数 $\varphi$$\phi$，以及三个聚合函数 $\rho$$\rho$ ：

   $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}})\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})\\ {\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right)\\ {\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})\end{array}$$

   其中：

   $${\mathcal{E}}_i^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{r_k=i,k=1,\cdots ,N_e},{\mathcal{E}}^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{k=1,\cdots ,N_e},{\mathcal{V}}^{\prime }={\left\{{\overrightarrow{\mathbf{v}}}_i^{\prime }\right\}}_{i=1,\cdots ,N_v}$$

   其物理意义为：

   • ${\varphi }^{(e)}$$\phi^{(e)}$ 根据每条边的属性 ${\overrightarrow{\mathbf{e}}}_k$$\mathbf{\vec e}_k$、全局属性 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$、以及 sender 节点属性 ${\overrightarrow{\mathbf{v}}}_{s_k}$$\mathbf{\vec v}_{s_k}$、receiver节点属性 ${\overrightarrow{\mathbf{v}}}_{r_k}$$\mathbf{\vec v}_{r_k}$来更新对应边的属性 ${\overrightarrow{\mathbf{e}}}_k^{\prime }$$\mathbf{\vec e}_k^\prime$。

   • ${\varphi }^{(v)}$$\phi^{(v)}$ 根据每个节点的属性 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$、全局属性 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$、以及 receiver为当前节点的所有边的属性（更新后的边属性）聚合后的 ${\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }$$\bar{\mathbf{\vec e}}_i^\prime$ 来更新对应节点的属性 ${\overrightarrow{\mathbf{v}}}_i^{\prime }$$\mathbf{\vec v}_i^\prime$ 。

   • ${\varphi }^{(u)}$$\phi^{(u)}$ 根据全局属性 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$、所有节点的属性（更新后）聚合后的 ${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }$$\bar{\mathbf{\vec v}}^\prime$ 、所有边的属性（更新后）聚合后的 ${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }$$\bar{\mathbf{\vec e}}^\prime$ 来更新全局属性 ${\overrightarrow{\mathbf{u}}}^{\prime }$$\mathbf{\vec u}^\prime$ 。它仅更新一次。

   • 每个 $\rho$$\rho$ 函数使用一个集合作为输入，然后聚合为单个结果代表聚合后的信息。最重要的是：$\rho$$\rho$ 函数必须是排列无关的（permutation invariant），并且应该采用可变数量的自变量。一些典型的例子包括：逐元素求和、均值池化、最大值池化等。

2. GN 块的计算步骤：

   • 通过执行 ${\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}})$$\phi^{(e)}\left(\mathbf{\vec e}_k, \mathbf{\vec v}_{r_k}, \mathbf{\vec v}_{s_k},\mathbf{\vec u}\right)$ 得到每条边更新后的属性 ${\overrightarrow{\mathbf{e}}}_k^{\prime }$$\mathbf{\vec e}_k^\prime$ 。在我们的弹簧示例中，${\varphi }^{(e)}$$\phi^{(e)}$ 可能对应于两个连接的橡胶球之间弹簧的力或者势能。

     • 更新后，边的集合为 ${\mathcal{E}}^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{k=1,\cdots ,N_e}$$\mathcal E^\prime = \left\{\left(\mathbf{\vec e}_k^\prime, r_k, s_k\right)\right\}_{k=1,\cdots,N_e}$ 。

     • 更新后，节点 $i$$i$ 相关的边的集合为 ${\mathcal{E}}_i^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{r_k=i,k=1,\cdots ,N_e}$$\mathcal E_i^\prime = \left\{\left(\mathbf{\vec e}_k^\prime, r_k, s_k\right)\right\}_{r_k=i,k=1,\cdots,N_e}$ 。这里节点 $i$$i$ 为 receiver 。

   • 执行 ${\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)$$\bar{\mathbf{\vec e}}_i^\prime = \rho^{(e\rightarrow v)}\left(\mathcal E_i^\prime\right)$ 从而得到每个节点对应边的聚合信息。在我们的弹簧示例中，${\rho }^{(e\to v)}$$\rho^{(e\rightarrow v)}$可能对应于作用在第 $i$$i$ 个球上所有力或势能的总和。

   • 通过执行 ${\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})$$\mathbf{\vec v}_i^\prime = \phi^{(v)}\left(\bar{\mathbf{\vec e}}_i^\prime, \mathbf{\vec v}_{i},\mathbf{\vec u}\right)$ 得到每个节点更新后的属性。在我们的弹簧示例中，${\varphi }^{(v)}$$\phi^{(v)}$ 可能更新类似于每个球的位置、速度、动能等。

     更新后，所有节点的属性集合为 ${\mathcal{V}}^{\prime }={\left\{{\overrightarrow{\mathbf{v}}}_i^{\prime }\right\}}_{i=1,\cdots ,N_v}$$\mathcal V^\prime = \left\{\mathbf{\vec v}_i^\prime\right\}_{i=1,\cdots,N_v}$ 。

   • 通过执行 ${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right)$$\bar{\mathbf{\vec e}}^\prime = \rho^{(e\rightarrow u)}\left(\mathcal E^\prime \right)$ 对所有边进行聚合得到 ${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }$$\bar{\mathbf{\vec e}}^\prime$ 。在我们的弹簧示例中，${\rho }^{(e\to u)}$$\rho^{(e\rightarrow u)}$ 可能计算力的总和（根据牛顿第三定律，总和应该为零）、弹簧势能的总和。

   • 通过执行 ${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right)$$\bar{\mathbf{\vec v}}^\prime = \rho^{(v\rightarrow u)}\left(\mathcal V^\prime\right)$ 对所有节点进行聚合得到 ${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }$$\bar{\mathbf{\vec v}}^\prime$ 。在我们的弹簧示例中 ${\rho }^{(v\to u)}$$\rho^{(v\rightarrow u)}$ 可能计算系统的总动能。

   • 通过执行 ${\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})$$\mathbf{\vec u}^\prime = \phi^{(u)}\left(\bar{\mathbf{\vec e}}^\prime, \bar{\mathbf{\vec v}}^\prime,\mathbf{\vec u}\right)$ 来更新图的全局属性。在我们的弹簧示例中， ${\varphi }^{(u)}$$\phi^{(u)}$ 可能会计算出类似于物理系统的总外力或总能量的值。

   尽管这里我们给出了计算步骤的顺序，但是并不是严格地根据这个顺序来执行。例如，可以先更新全局属性、再更新节点属性、最后更新边属性。

3. GN block 更新函数 GraphNETWORK()：

   • 输入：图 $\mathcal{G}=(\overrightarrow{\mathbf{u}},\mathcal{V},\mathcal{E})$$\mathcal G = \left(\mathbf{\vec u},\mathcal V, \mathcal E\right)$，其中 $\mathcal{V}$$\mathcal V$ 为节点属性集合、 $\mathcal{E}$$\mathcal E$ 为边集合、 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 为全局属性

   • 输出：更新后的图 ${\mathcal{G}}^{\prime }=({\overrightarrow{\mathbf{u}}}^{\prime },{\mathcal{V}}^{\prime },{\mathcal{E}}^{\prime })$$\mathcal G^\prime = \left(\mathbf{\vec u}^\prime,\mathcal V^\prime, \mathcal E^\prime\right)$

   • 计算步骤：

     • 迭代更新边的属性：$k\in \{1,\cdots ,N_e\}$$k\in \{1,\cdots,N_e\}$ ，执行 ${\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}})$$\mathbf{\vec e}_k^\prime = \phi^{(e)}\left(\mathbf{\vec e}_k, \mathbf{\vec v}_{r_k}, \mathbf{\vec v}_{s_k},\mathbf{\vec u}\right)$ 。

     • 迭代更新节点的属性：$i\in \{1,\cdots ,N_v\}$$i\in \{1,\cdots,N_v\}$ ，执行：

       • 令 ${\mathcal{E}}_i^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{r_k=i,k=1,\cdots ,N_e}$$\mathcal E_i^\prime = \left\{\left(\mathbf{\vec e}_k^\prime, r_k, s_k\right)\right\}_{r_k=i,k=1,\cdots,N_e}$ 表示所有 receiver 为当前节点 $i$$i$ 的边的集合。

       • 聚合 ${\mathcal{E}}_i^{\prime }$$\mathcal E_i^\prime$ 中所有边的信息 ${\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)$$\bar{\mathbf{\vec e}}_i^\prime = \rho^{(e\rightarrow v)}\left(\mathcal E_i^\prime\right)$ 。

       • 更新节点属性 ${\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})$$\mathbf{\vec v}_i^\prime = \phi^{(v)}\left(\bar{\mathbf{\vec e}}_i^\prime, \mathbf{\vec v}_{i},\mathbf{\vec u}\right)$ 。

     • 令 ${\mathcal{V}}^{\prime }={\left\{{\overrightarrow{\mathbf{v}}}_i^{\prime }\right\}}_{i=1,\cdots ,N_v}$$\mathcal V^\prime = \left\{\mathbf{\vec v}_i^\prime\right\}_{i=1,\cdots,N_v}$ 为所有节点更新后的属性，聚合所有节点属性为 ${\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right)$$\bar{\mathbf{\vec v}}^\prime = \rho^{(v\rightarrow u)}\left(\mathcal V^\prime\right)$ 。

     • 令 ${\mathcal{E}}^{\prime }={\left\{({\overrightarrow{\mathbf{e}}}_k^{\prime },r_k,s_k)\right\}}_{k=1,\cdots ,N_e}$$\mathcal E^\prime = \left\{\left(\mathbf{\vec e}_k^\prime, r_k, s_k\right)\right\}_{k=1,\cdots,N_e}$ 为所有边更新后的属性，聚合所有边属性为 ${\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right)$$\bar{\mathbf{\vec e}}^\prime = \rho^{(e\rightarrow u)}\left(\mathcal E^\prime \right)$ 。

     • 根据全局属性、聚合后的节点属性、聚合后的边属性来更新全局属性 ${\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})$$\mathbf{\vec u}^\prime = \phi^{(u)}\left(\bar{\mathbf{\vec e}}^\prime, \bar{\mathbf{\vec v}}^\prime,\mathbf{\vec u}\right)$ 。

     • 返回更新后的图 ${\mathcal{G}}^{\prime }=({\overrightarrow{\mathbf{u}}}^{\prime },{\mathcal{V}}^{\prime },{\mathcal{E}}^{\prime })$$\mathcal G^\prime = \left(\mathbf{\vec u}^\prime,\mathcal V^\prime, \mathcal E^\prime\right)$ 。

4. 给定一个图 $\mathcal{G}=(\overrightarrow{\mathbf{u}},\mathcal{V},\mathcal{E})$$\mathcal G = \left(\mathbf{\vec u},\mathcal V, \mathcal E\right)$ 作为 GN 块的输入时，计算过程从边、节点、global-level。下图给出了这些计算中，每一个计算都涉及哪些图元素。蓝色表示待更新的元素，黑色表示更新中涉及的其它元素（注意，蓝色元素更新之前的值也用于它的本次更新）。

   

   下图给出了具有更新函数、聚合函数的完整 GN 块。它根据输入的节点属性、边属性、全局属性来预测输出的节点属性、边属性、全局属性。

   

1.2.3 关系归纳偏置

1. 当用于 learning process 的组成部分时，我们的 GN 框架会强制添加几个很强的关系归纳偏置：

   • 首先，图可以表达实体之间的任意关系。这意味着 GN 的输入决定了 representation 是如何交互（interact）和隔离（isolated）的，而不是由固定（fixed）的体系架构来决定的。

     即实体的交互和隔离是由数据决定，而不是由模型决定。

     例如：

     • 如果两个实体对应的节点之间存在边，则认为这两个实体之间有关联，即有交互。

     • 如果两个实体对应的节点之间不存在边，则认为这两个实体之间没有关联，即隔离的。

   • 其次，图将实体及其关系表示为集合，这是排列不变的（permutation invariant）。这意味着 GN 对于这些元素的顺序是不敏感的，这通常是我们所需要的。

   • 最后，GN 的 per-edge 函数、per-node 函数分别在所有边、所有节点之间重用。这意味着 GN 自动支持某种形式的组合泛化：由于图由边、节点、以及全局属性组成，因此单个 GN 可以在不同大小（以边和节点数量刻画）、不同形状（不同的连通性）的图上进行操作。

1.3 GN 设计原则

1. 根据前述列出的设计原则，GN 框架可用于实现各种各样的体系架构。通常，GN 框架和特定的属性表示（attribute representation）和函数形式（functional form）无关。但是这里我们重点关注深度学习架构，该架构允许 GN 充当可学习的 graph-to-graph 的函数逼近器（function approximator）。

2. 这里再回顾一下 GN 设计原则：灵活的表示（flexible representations）、可配置的块内结构（congurable within-block structure）、可组合的多块体系架构（composable multi-block architectures）。

   这三个设计原则再我们的 GN 框架中结合在一起，非常灵活，适用于从感知、语言、到符号推理的广泛领域。并且，如前所述，GN 具有的强大的关系归纳偏置支持组合泛化，因此使得 GN 在实际和理论上都成为强大的工具。

1.3.1 Flexible Representations

1. 灵活的表示有两层含义：

   • 属性形式：GN 块的全局属性、节点属性、边属性可以为任意表示形式（arbitrary representational formats）。

   • 图结构形式：输入数据可以包含关系结构，或者不包含关系结构，即输入数据的图结构形式可以任意。

2. 属性形式：GN 块的全局属性、节点属性、边属性可以使用任意表示形式。在深度学习实现中，通常使用实值向量或张量。但是，也可以使用其它数据结构，如序列（sequence）、集合（set）、甚至是图（graph）。

   • 通常我们需要决定：对某个问题采用何种表示形式来描述属性。例如：

     • 当输入数据是图像时，节点属性可以为图像 patches 的张量。

     • 当输入数据为文档时，节点属性可以为句子对应的单词序列。

   • 对于更广泛的体系架构中的每个 GN 块，每个边/节点的输出通常对应于一个张量/向量，而全局输出对应于单个张量/向量。这使得 GN 块的输出可以传递到其它深度学习构建块（building block）中，如 MLP,CNN,RNN 。GN 块的输出也可以根据任务需求进行定制化。具体而言：

     • edge-focused GN 可以仅仅将边作为输出。例如，做出有关实体之间相互作用的决策。

     • node-focused GN 可以仅仅将节点作为输出。例如，用于推理物理系统。

     • graph-focused GN 可以仅仅将全局属性作为输出。例如，预测物理系统的势能、分子性质、关于某个视觉场景问题的答案。

     节点属性、边属性、全局属性的输出也可以根据任务混合使用。

3. 图结构形式：在定义如何将输入数据表示为图结构时，有两种情形：

   • 首先，输入数据明确指定了关系结构。例如：知识图谱、社交网络、化学分子图、交通网络、以及具有已知交互作用的物理系统。

   • 其次，需要从输入数据中推断或假设关系结构，即关系结构没有明确指定。例如视觉场景、文本文档等。

     • 这里可以将数据表示为一组没有关系的实体，甚至仅表示为向量或张量（如：图像）。

       如果未明确指定实体，则可以通过将诸如句子中的每个单词、或者 CNN 输出 feature map 中的 feature vector 视为节点来指定实体。

       或者，也可以使用单独的学习机制从非结构化信号中推断实体，如通过解析树算法从文本中得到解析树。

     • 如果关系不可用，则最简单的方法是在实体之间添加所有可能的有向边。如在图像的 patches 之间两两添加有向边。但是，这对于拥有大量实体的图而言是不可行的，因为边的数量会随着节点数量的增加而平方规模的增加。

       因此，研发更复杂的方法来从非结构化数据中推断稀疏的图结构是未来的重要方向。

1.3.2 Configurable Within-block Structure

1. GN 块中的结构和函数可以通过不同的方式进行配置，从而可以灵活地确定哪些信息可以用作函数的输入，以及如何更新边属性、节点属性、全局属性。具体而言，GN 块中的每个 $\varphi$$\phi$ 函数必须实现为某种函数 $f$$f$，其中 $f$$f$ 的自变量签名（argument signature）决定了它需要哪些信息作为输入。

   通过选择不同的函数 $f$$f$ 和块内配置，GN 框架可以表达其它各种架构，如下图所示。接下来讨论如何使用不同的方式配置 GN 的块内结构。

   下图中，每个 $\varphi$$\phi$ 的incoming 箭头表示是否将 $\overrightarrow{\mathbf{u}},\mathcal{V},\mathcal{E}$$\mathbf{\vec u}, \mathcal V, \mathcal E$ 用作输入。

   • (a)：full GN （即完整的、原始的 GN 块）根据传入的节点属性、边属性、全局属性来输出节点属性、边属性、全局属性。

   • (b)：独立的循环块使用 input 和 hidden state 来进行更新，其中 $\varphi$$\phi$ 函数为 RNN 。

   • (c)：MPNN 根据传入的节点属性、边属性来输出节点属性、边属性、全局属性。注意，全局预测中不包含聚合的边，输入中不包含全局属性。

   • (d)：NLNN 仅输出节点属性。

   • (e)：Relation Network 仅使用预测的边属性来输出全局属性。

   • (f)：Deep Set 没有采用边更新从而输出全局属性。

   

    

2. Full GN block：《Relational inductive bias for physical construction in humans and machines》 和 《Graph networks as learnable physics engines for inference and control》 使用完整的 GN 块，如上图的 (a) 所示。

   • 他们使用神经网络来实现 $\varphi$$\phi$ 函数，用 ${\text{NN}}_e,{\text{NN}}_v,{\text{NN}}_u$$\text{NN}_e, \text{NN}_v, \text{NN}_u$ 分别表示 ${\varphi }^{(e)},{\varphi }^{(v)},{\varphi }^{(u)}$$\phi^{(e)},\phi^{(v)},\phi^{(u)}$ ，其中不同的下标表示这些函数是具有不同参数的不同函数。

   • 他们的 $\rho$$\rho$ 函数采用逐元素求和来实现，但是也可以采用均值池化或最大/最小池化。

   更新方程为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}})={\text{NN}}_e\left([{\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}]\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right):=\sum _{k:r_k=i}{\overrightarrow{\mathbf{e}}}_k^{\prime }\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}]\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right):=\sum _k{\overrightarrow{\mathbf{e}}}_k^{\prime }\\ {\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}}):=f^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})={\text{NN}}_u\left([{\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}}]\right)\\ {\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right):=\sum _i{\overrightarrow{\mathbf{v}}}_i^{\prime }\end{array}$$

   其中：

   • $[\cdot ,\cdot ,\cdot ]$$[\cdot,\cdot,\cdot]$ 表示向量拼接。

   • 对于向量属性，通常采用 MLP 作为 $\varphi$$\phi$ 函数；对于张量属性（如图像的 feature map），通常采用 CNN 作为 $\varphi$$\phi$ 函数。

3. $\varphi$$\phi$ 函数也可以使用 RNN，这需要额外的 hidden state 作为输入和输出。上图 (b) 展示了一个非常简单的 GN 块，其中 RNN 作为 $\varphi$$\phi$ 函数。公式中没有消息传递，并且这种类型的 block 可用于对某些 dynamic graph state 进行递归平滑（recurrent smoothing）。

   当然，RNN 作为 $\varphi$$\phi$ 函数也可以在 full GN block 中使用。

4. Message-passing neural network: MPNN 概括了很多之前的体系架构，并且可以很自然地转换为 GN 的格式：

   • 消息函数 $M_t(\cdot )$$M_t(\cdot)$ 扮演 GN 中的 ${\varphi }^{(e)}$$\phi^{(e)}$ 的角色，但是没有使用 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 作为输入。

   • GN 的 ${\rho }^{(e\to v)}$$\rho^{(e\rightarrow v)}$ 采用逐元素累加。

   • 更新函数 $U_t(\cdot )$$U_t(\cdot)$ 扮演 GN 中的 ${\varphi }^{(v)}$$\phi^{(v)}$ 的角色。

   • readout 函数 $R(\cdot )$$R(\cdot)$ 扮演 GN 中的 ${\varphi }^{(u)}$$\phi^{(u)}$ 的角色，但是没有使用 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 和 ${\mathcal{E}}^{\prime }$$\mathcal E^\prime$ 作为输入，因此不需要 GN 的 ${\rho }^{(e\to u)}$$\rho^{(e\rightarrow u)}$ 函数。

   • $d_{\text{master}}$$d_{\text{master}}$ 的作用和 GN 中的 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 大致相似，但是被定义为与所有其它节点相连的附加节点，因此不会直接影响边属性和全局属性更新。并且它被包含在 GN 的 $\mathcal{V}$$\mathcal V$ 中。

   上图 (c) 展示了如何根据 GN 块来构建 MPNN。

5. Non-local Neural Networks:NLNN 统一了各种 intra/self/vertex/graph attention 方法，它也可以转换为 GN 的格式。

   attention 指的是节点的更新方式：每个节点更新均基于其邻域节点属性（或者它的某些函数）的加权和，其中一个节点和它某个邻居之间的权重由属性之间的 scale pairwise 函数（然后整个邻域归一化）给出。

   已发表的 NLNN 公式并未显式包含边，而是计算所有节点之间的 pairwise 注意力权重。但是，各种 NLNN-compliant 模型，例如节点注意力交互网络（vertex attention interaction network）、图注意力网络（graph attention network）都可以通过有效地将没有边的节点之间的权重设为零来显式处理边。

   在 NLNN 中， ${\varphi }^{(e)}$$\phi^{(e)}$ 被乘以一个标量的 pairwise-interaction 函数，该函数返回：

   • 未归一化的 attention 系数，记作 ${\alpha }^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})=a_k^{\prime }$$\alpha^{(e)} \left(\mathbf{\vec v}_{r_k},\mathbf{\vec v}_{s_k}\right) = a_k^\prime$ 。

   • 一个 non-pairwise 的向量值，记作 ${\beta }^{(e)}({\overrightarrow{\mathbf{v}}}_{s_k})={\overrightarrow{\mathbf{b}}}_k^{\prime }$$\beta^{(e)}(\mathbf{\vec v}_{s_k}) = \mathbf{\vec b}_k^\prime$ 。

   在 ${\rho }^{(e\to v)}$$\rho^{(e\rightarrow v)}$ 聚合中，$a_k^{\prime }$$a_k^\prime$ 在 receiver 的所有边上归一化，然后 ${\overrightarrow{\mathbf{b}}}_k^{\prime }$$\mathbf{\vec b}_k^\prime$ 进行逐元素相加：

   $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})=({\alpha }^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k}),{\beta }^{(e)}({\overrightarrow{\mathbf{v}}}_{s_k}))=(a_k^{\prime },{\overrightarrow{\mathbf{b}}}_k^{\prime })\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}\left({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right):=\frac{\sum _{r_k=i}{a}_k^{\prime }{\overrightarrow{\mathbf{b}}}_k^{\prime }}{\sum _{r_k=i}{a}_k^{\prime }}\end{array}$$

   在 NLNN 论文中，$f(\cdot )$$f(\cdot)$ 函数扮演上述 $\alpha$$\alpha$ 的角色，$g(\cdot )$$g(\cdot)$ 函数扮演上述 $\beta$$\beta$ 的角色。 这个公式可能有助于仅关注于下游任务最相关的那些交互，尤其是当输入实体是一个集合set（而不是图graph）、并且这个图是根据集合中所有实体之间添加所有可能的边来构建的。

   • Transformer 体系架构中的 single-headed self-attention，即 SA， 实现为公式为：

     $$\begin{array}{c}{a}_k^{\prime }={\alpha }^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})=\exp \left({\text{NN}}_{\alpha ,query}{\left({\overrightarrow{\mathbf{v}}}_{r_k}\right)}^{\mathrm{\top }}{\text{NN}}_{\alpha ,key}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\right)\\ {\overrightarrow{\mathbf{b}}}_k^{\prime }={\beta }^{(e)}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)={\text{NN}}_{\beta }\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}\left({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }\right)={\text{NN}}_v\left({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }\right)\end{array}$$

     其中 ${\text{NN}}_{\alpha ,query},{\text{NN}}_{\alpha ,key},{\text{NN}}_{\beta }$$\text{NN}_{\alpha,query}, \text{NN}_{\alpha,key},\text{NN}_{\beta}$ 都是神经网络函数，使用不同的参数、甚至不同的架构。

   • 《Attention is all you need》 的 multi-head self-attention 机制增加了一个有趣的特性： ${\varphi }^{(e)}$$\phi^{(e)}$ 和 ${\rho }^{(e\to v)}$$\rho^{(e\rightarrow v)}$ 通过一组并行的函数来实现，它们的结果拼接在一起作为最终的 ${\rho }^{(e\to v)}$$\rho^{(e\rightarrow v)}$ 。这可以解释为使用不同类型的边，其中不同类似索引到不同的 ${\varphi }^{(e)}$$\phi^{(e)}$ 分量函数，类似于 Gated Graph Sequence Neural Networks 。

     具体而言，multi-head self-attention 计算 $H$$H$ 个并行的 ${\left\{{\overline{\overrightarrow{\mathbf{e}}}}_{i,h}^{\prime }\right\}}_{h=1,\cdots ,H}$$\left\{\bar{\mathbf{\vec e}}_{i,h}^\prime\right\}_{h=1,\cdots,H}$：

     $${\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}\left({\left\{{\overline{\overrightarrow{\mathbf{e}}}}_{i,h}^{\prime }\right\}}_{h=1,2,\cdots ,H}\right)={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_{i,1}^{\prime },\cdots ,{\overline{\overrightarrow{\mathbf{e}}}}_{i,H}^{\prime }]\right)$$

   • Vertex Attention Interaction Networks 和 SA 很相似，但是它将欧几里得距离用于 attention 相似性度量，并在 attention 输入的 embedding 中共享参数，且在节点更新函数中使用节点的输入特征：

     $$\begin{array}{c}{a}_k^{\prime }={\alpha }^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})=\exp (-{\Vert {\text{NN}}_{\alpha }\left({\overrightarrow{\mathbf{v}}}_{r_k}\right)-{\text{NN}}_{\alpha }\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\Vert }^2)\\ {\overrightarrow{\mathbf{b}}}_k^{\prime }={\beta }^{(e)}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)={\text{NN}}_{\beta }\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i)={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i]\right)\end{array}$$

   • Graph Attention Networks 和 multi-head self-attention 相似，但是它使用神经网络作为 attention 相似性度量，并在 attention 输入的 embedding 中共享参数：

     $$\begin{array}{c}{a}_{k,h}^{\prime }={\alpha }_h^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})=\exp \left({\text{NN}}_{{\alpha }^{\prime },h}({\text{NN}}_{\alpha ,h}\left({\overrightarrow{\mathbf{v}}}_{r_k}\right),{\text{NN}}_{\alpha ,h}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right))\right)\\ {\overrightarrow{\mathbf{b}}}_{k,h}^{\prime }={\beta }_h^{(e)}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)={\text{NN}}_{\beta ,h}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}\left({\left\{{\overline{\overrightarrow{\mathbf{e}}}}_{i,h}^{\prime }\right\}}_{h=1,\cdots ,H}\right)={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_{i,1}^{\prime },\cdots ,{\overline{\overrightarrow{\mathbf{e}}}}_{i,H}^{\prime }]\right)\end{array}$$

   • 《Self-attention with relative position representations》 提出相对位置编码（ relative position encodings ）来扩展 multi-head self-attention。relative 是指对序列中节点之间的空间距离进行编码、或度量空间中其它信号进行编码。这可以在 GN 中表示为边的属性 ${\overrightarrow{\mathbf{e}}}_k$$\mathbf{\vec e}_k$ ，并将 multi-head self-attention 中的 ${\beta }^{(e)}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)$$\beta^{(e)}\left(\mathbf{\vec v}_{s_k}\right)$ 替换为：

     $${\overrightarrow{\mathbf{b}}}_k^{\prime }={\beta }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{s_k})={\text{NN}}_{\beta }\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)+{\overrightarrow{\mathbf{e}}}_k$$

   下图展示了如何在 GN 框架下通过 ${\varphi }^{(e)}$$\phi^{(e)}$ 和 ${\rho }^{(e\to v)}$$\rho^{(e\rightarrow v)}$ 来实现NLNN 。 通常 NLNN 假设图像（或句子中的单词）对应于全连接图中的节点，并假设注意力机制在聚合步骤中定义节点上的加权和。

   

6. 完整的 GN block 公式可以预测完整的图 ${\mathcal{G}}^{\prime }=({\overrightarrow{\mathbf{u}}}^{\prime },{\mathcal{V}}^{\prime },{\mathcal{E}}^{\prime })$$\mathcal G^\prime= (\mathbf{\vec u}^\prime,\mathcal V^\prime, \mathcal E^\prime)$ ，或者它的一部分。例如，为了预测图的全局属性，${\mathcal{V}}^{\prime },{\mathcal{E}}^{\prime }$$\mathcal V^\prime,\mathcal E^\prime$ 可以被忽略。类似地，如果在输入中未给出全局属性、节点属性或边属性，则对应的部分可以忽略，即不作为 $\varphi$$\phi$ 函数的输入。

   同样的思路可以适用于其它 GN 变体，这些变体不使用完整的 mapping $\varphi$$\phi$ 函数、或不使用完整的 reduction $\rho$$\rho$ 函数。

   • Interaction Networks 和 Neural Physics Engine 使用 full GN，但是没有使用全局属性来更新边属性。

     $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})={\text{NN}}_e\left([{\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k}]\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}]\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)=\sum _{k:r_k=i}{\overrightarrow{\mathbf{e}}}_k^{\prime }\end{array}$$

     该工作还包括对上述公式的扩展：输出全局的、而不是 per-node 的预测：

     $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})={\text{NN}}_e\left([{\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k}]\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}]\right)\\ {\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}}):=f^{(u)}({\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}})={\text{NN}}_u\left([{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}}]\right)\\ {\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right):=\sum _i{\overrightarrow{\mathbf{v}}}_i^{\prime }\end{array}$$

     这里没有使用全局属性来更新边属性，也没有用边属性来更新全局属性。

   • Relation Networks 完全绕开了节点更新，并直接从池化的边信息中预测全局属性输出：

     $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k})={\text{NN}}_e\left([{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k}]\right)\\ {\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}({\overline{\overrightarrow{\mathbf{e}}}}^{\prime },{\overline{\overrightarrow{\mathbf{v}}}}^{\prime },\overrightarrow{\mathbf{u}}):=f^{(u)}\left({\overline{\overrightarrow{\mathbf{e}}}}^{\prime }\right)={\text{NN}}_u\left({\overline{\overrightarrow{\mathbf{e}}}}^{\prime }\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}^{\prime }={\rho }^{(e\to u)}\left({\mathcal{E}}^{\prime }\right):=\sum _k{\overrightarrow{\mathbf{e}}}_k^{\prime }\end{array}$$

   • Deep Sets 完全绕开了边更新，并直接根据池化的节点信息中预测全局属性输出：

     $$\begin{array}{c}{\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}})={\text{NN}}_v\left([{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}]\right)\\ {\overrightarrow{\mathbf{u}}}^{\prime }={\varphi }^{(u)}\left({\overline{\overrightarrow{\mathbf{v}}}}^{\prime }\right):=f^{(u)}\left({\overline{\overrightarrow{\mathbf{v}}}}^{\prime }\right)={\text{NN}}_u\left({\overline{\overrightarrow{\mathbf{v}}}}^{\prime }\right)\\ {\overline{\overrightarrow{\mathbf{v}}}}^{\prime }={\rho }^{(v\to u)}\left({\mathcal{V}}^{\prime }\right):=\sum _i{\overrightarrow{\mathbf{v}}}_i^{\prime }\end{array}$$

   • PointNet 使用类似的更新规则，但是对于${\rho }^{v\to u}$$\rho^{v\rightarrow u}$ 使用最大池化，以及对于节点更新使用两阶段。

   • Gated Graph Sequence Neural Networks: GGS-NN 使用稍微泛化的公式，其中每条边关联一个类别 $t_k\in \{1,\cdots ,T\}$$t_k\in \{1,\cdots,T\}$ ，更新公式为：

     $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}(({\overrightarrow{\mathbf{e}}}_k,t_k),{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{s_k})={\text{NN}}_{e,t_k}\left(\left[{\overrightarrow{\mathbf{v}}}_{s_k}\right]\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i)={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i]\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)=\sum _{k:r_k=i}{\overrightarrow{\mathbf{e}}}_k^{\prime }\end{array}$$

     这里 ${\text{NN}}_v$$\text{NN}_v$ 为一个 GRU， ${\text{NN}}_{e,t_k}$$\text{NN}_{e,t_k}$ 为待特定参数的神经网络。

     上述更新递归进行，然后接一个全局解码器，该解码器计算所有节点的最终 embedding 的加权和。

   • CommNet 的更新公式为：

     $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)={\text{NN}}_e\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i,\overrightarrow{\mathbf{u}}):=f^{(v)}({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\overrightarrow{\mathbf{v}}}_i)={\text{NN}}_v\left([{\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime },{\text{NN}}_{v^{\prime }}\left({\overrightarrow{\mathbf{v}}}_i\right)]\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }={\rho }^{(e\to v)}\left({\mathcal{E}}_i^{\prime }\right)=\frac{1}{|{\mathcal{E}}_i^{\prime }|}\sum _{k:r_k=i}{\overrightarrow{\mathbf{e}}}_k^{\prime }\end{array}$$

   • structure2vec 也可以适配我们的算法，只需要进行少量的修改：

     $$\begin{array}{c}{\overline{\overrightarrow{ϵ}}}_k=\rho \left({\left\{{\overrightarrow{\mathbf{e}}}_l\right\}}_{s_l=r_k,r_l\ne s_k}\right):=\sum _{s_l=r_k,r_l\ne s_k}{\overrightarrow{\mathbf{e}}}_l\\ {\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}\left({\overline{\overrightarrow{ϵ}}}_k\right):=f\left({\overline{\overrightarrow{ϵ}}}_k\right)=\text{NN}\left({\overline{\overrightarrow{ϵ}}}_k\right)\\ {\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }=\rho \left({\left\{{\overrightarrow{\mathbf{e}}}_k^{\prime }\right\}}_{r_k=i}\right):=\sum _{k:r_k=i}{\overrightarrow{\mathbf{e}}}_k^{\prime }\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }={\varphi }^{(v)}\left({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }\right):=f\left({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }\right)=\text{NN}\left({\overline{\overrightarrow{\mathbf{e}}}}_i^{\prime }\right)\end{array}$$

     其中 $s_l=r_k,r_l\ne s_k$$s_l=r_k,r_l\ne s_k$ 表示以第 $k$$k$ 条边的终点为起点的所有边，并剔除以第 $k$$k$ 条边的终点为起点的边。

     边的属性现在在 receiver 和 sender 之间具有 message 的含义。注意，对于边和节点更新，现在只有一组参数需要学习。

   注意：对于 CommNet、structure2vec、Graph Sequence Neural Networks 使用一种非对称的 ${\varphi }^{(e)}$$\phi^{(e)}$ ，它并未计算 pairwise interaction，而是忽略receiver node 而仅考虑 sender 节点，并且某种程度上是在边属性上进行。这种做法可以通过具有以下签名 signature 的 ${\varphi }^{(e)}$$\phi^{(e)}$ 函数上实现：

   $$\begin{array}{c}{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}\left({\overrightarrow{\mathbf{v}}}_{s_k}\right)\\ \text{ or }{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):={\overrightarrow{\mathbf{v}}}_{s_k}+f^{(e)}\left({\overrightarrow{\mathbf{e}}}_k\right)\\ \text{ or }{\overrightarrow{\mathbf{e}}}_k^{\prime }={\varphi }^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{r_k},{\overrightarrow{\mathbf{v}}}_{s_k},\overrightarrow{\mathbf{u}}):=f^{(e)}({\overrightarrow{\mathbf{e}}}_k,{\overrightarrow{\mathbf{v}}}_{s_k})\end{array}$$

   .